<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>План лекций</title>
  <link href=styles/styles.css rel="stylesheet" type="text/css">
</head>
<h2>День 6. Длинная арифметика, численные методы.</h2>
<ol>
  <li>Умножение матриц</li>
  <ol>
    <li>Умножение матриц за O(n<sup>3</sup>), правильный порядок (for i) (for j) и (for k)</li>
    <li>Битовое сжатие: умножение битовых матриц по модулю 2 за O(n<sup>3</sup>/ logn)</li>
    <li>Метод четырех-русских для умножения битовых матриц по модулю 2 за O(n<sup>3</sup>/ log<sup>2</sup>n)</li>
    <li>Метод Штрассена за O(n<sup>2.8</sup>)</li>
  </ol></li>
  <li>Длинная арифметика</li>
  <ol>
    <li>Оптимальное умножение за O(n<sup>2</sup>)</li>
    <li>Карацуба: O(n<sup>1.6</sup>)</li>
    <li>Фурье: O(nlogn)</li>
    <li>Нерекурсивная реализация Фурье</li>
    <li>Оптимальное написание Фурье</li>
    <li>Метод Ньютона для функций R &rarr; R. Общее описание.</li>
    <li>Деление чисел за O(nlogn) через Фурье и метод Ньютона</li>
    <li>Квадратный корень за O(nlogn) через Фурье и метод Ньютона</li>
    <li>Квадратный корень с использованием только одного деления (итого: константа меньше)</li>
  </ol></li>
  <li>Читы: Быстрые проверки</li>
  <ol>
    <li>A*B = C за O(n<sup>2</sup>)</li>
    <li>det A = 0 за O(n<sup>3</sup>)</li>
    <li>expr1 = expr2 за O(n)</li>
  </ol></li>
  <li>Численные методы. Метод итераций</li>
  <ol>
    <li><span style="color: blue;"><i>Not read </i></span>Решение систем линейных уравнений.</li>
    <li>Решение задач про теорвер возведением матрицы в степень.</li>
    <li>Нормализация матриц.</li>
  </ol></li>
  <li>Численные методы. Корни, максимумы.</li>
  <ol>
    <li>Корень &harr; max</li>
    <li>min &harr; max</li>
    <li>Бинарный поиск (корень функции)</li>
    <li>Троичный поиск</li>
    <ol>
      <li>Локальный минимум для любой выпуклой тройки</li>
      <li>Переиспользуем уже посчитанные значения</li>
      <li>Золотое сечение</li>
    </ol></li>
    <li>Глобальный минимум произвольной функции</li>
    <ol>
      <li>Разбили на куски, троичный поиск.</li>
      <li>Итеративно уменьшаем область [L,R], в которой лежит глобальный минимум.</li>
      <li>Чтобы найти 1 глобальный минимум можно попробовать честно найти все локальные. Метод поиска.</li>
    </ol></li>
  </ol></li>
  <li>Численные методы.</li>
  <ol>
    <li>Вещественные корни многочленов за O(n<sup>2</sup>logn).</li>
    <li>Комплексные корни многочленов градиентным спуском и случайным поиском.</li>
  </ol></li>
</ol>
